package com.lzh.others.leetcode.tree;

import java.util.HashMap;
import java.util.Map;

/**
 * 找出二叉树中相同的节点
 * 给你两棵二叉树，原始树 original 和克隆树 cloned，以及一个位于原始树 original 中的目标节点 target。
 * <p>
 * 其中，克隆树 cloned 是原始树 original 的一个 副本 。
 * <p>
 * 请找出在树 cloned 中，与 target 相同 的节点，并返回对该节点的引用（在 C/C++ 等有指针的语言中返回 节点指针，其他语言返回节点本身）。
 * <p>
 * <p>
 * <p>
 * 注意：你 不能 对两棵二叉树，以及 target 节点进行更改。只能 返回对克隆树 cloned 中已有的节点的引用。
 * 例子1：
 * 输入: tree = [7,4,3,null,null,6,19], target = 3
 * 输出: 3
 */
public class LeetCode1379 {

    private static Map<Integer, Integer> map = new HashMap<>(); // 存放节点值与索引之间的对应关系
    private static TreeNode orginal = null;

    static {
        System.out.println("hello world");
        Integer[] tree = new Integer[]{7, 4, 3, null, null, 6, 19};
        orginal = buildBinaryTree(tree);
    }


    public static class TreeNode {
        Integer val;
        TreeNode left;
        TreeNode right;

        TreeNode(Integer x) {
            val = x;
        }
    }


    static class Solution {
        public final TreeNode getTargetCopy(final TreeNode original, final TreeNode cloned, final TreeNode target) {
            TreeNode treeNode = new TreeNode(1);
            return treeNode;
        }
    }

    public static void main(String[] args) {
        Solution solution = new Solution();
    }

    public static TreeNode buildBinaryTree(Integer[] preorder) {
        if (preorder == null || preorder.length == 0) return null;

        for (int i = 0; i < preorder.length; i++) {
            map.put(i, preorder[i]); // 记录每个节点在数组中的位置
        }

        return constructBinaryTree(0, preorder.length - 1);
    }

    private static TreeNode constructBinaryTree(int start, int end) {
        if (start > end) return null;

        Integer value = map.get(start); // 获取当前节点的值
        TreeNode node = new TreeNode(value); // 创建新节点

        if (start != end) {
            int index = findIndexOfNextElement(start + 1, end); // 查找左子树的范围

            node.left = constructBinaryTree(start + 1, index); // 构造左子树
            node.right = constructBinaryTree(index + 1, end); // 构造右子树
        }

        return node;
    }

    private static int findIndexOfNextElement(int start, int end) {
        while (map.containsKey(end)) {
            end--;
        }

        return end;
    }

}
